/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / c / library / dos / diverses / leda / src / graph_al / matching.heu

< prev

MacOS 8.1

Win98

DOS

browse contents

view JSON data

view as text

+--------+-------------------------+-------------------------+--------+--------+
|00000000| 46 72 6f 6d 20 6d 61 72 | 6b 75 73 40 6d 70 69 69 |From mar|kus@mpii|
|00000010| 30 31 30 30 32 2e 63 73 | 2e 75 6e 69 2d 73 62 2e |01002.cs|.uni-sb.|
|00000020| 64 65 20 4d 6f 6e 20 4f | 63 74 20 32 38 20 31 31 |de Mon O|ct 28 11|
|00000030| 3a 30 38 3a 31 36 20 31 | 39 39 31 0a 46 72 6f 6d |:08:16 1|991.From|
|00000040| 3a 20 6d 61 72 6b 75 73 | 40 6d 70 69 69 30 31 30 |: markus|@mpii010|
|00000050| 30 32 2e 63 73 2e 75 6e | 69 2d 73 62 2e 64 65 0a |02.cs.un|i-sb.de.|
|00000060| 54 6f 3a 20 73 74 65 66 | 61 6e 0a 53 75 62 6a 65 |To: stef|an.Subje|
|00000070| 63 74 3a 20 47 65 6e 2e | 20 4d 61 74 63 68 69 6e |ct: Gen.| Matchin|
|00000080| 67 0a 0a 27 20 4d 6f 72 | 67 65 6e 2e 0a 0a 49 63 |g..' Mor|gen...Ic|
|00000090| 68 20 73 63 68 69 63 6b | 65 20 44 69 72 20 6d 61 |h schick|e Dir ma|
|000000a0| 6c 20 64 69 65 20 48 65 | 75 72 69 73 74 69 6b 2c |l die He|uristik,|
|000000b0| 20 64 69 65 20 28 66 61 | 73 74 29 20 61 6c 6c 65 | die (fa|st) alle|
|000000c0| 20 50 66 61 64 65 20 64 | 65 72 20 0a 4c 61 65 6e | Pfade d|er .Laen|
|000000d0| 67 65 20 3c 3d 20 33 20 | 66 69 6e 64 65 74 2e 20 |ge <= 3 |findet. |
|000000e0| 53 69 65 20 69 73 74 20 | 6b 61 75 6d 20 6c 61 6e |Sie ist |kaum lan|
|000000f0| 67 73 61 6d 65 72 20 61 | 6c 73 20 64 69 65 20 22 |gsamer a|ls die "|
|00000100| 47 72 65 65 64 79 22 2d | 4d 65 74 68 6f 64 65 2c |Greedy"-|Methode,|
|00000110| 0a 61 62 65 72 20 77 65 | 73 65 6e 74 6c 69 63 68 |.aber we|sentlich|
|00000120| 20 62 65 73 73 65 72 2e | 20 44 69 65 20 4c 61 75 | besser.| Die Lau|
|00000130| 66 7a 65 69 74 20 64 65 | 73 20 6e 61 63 68 66 6f |fzeit de|s nachfo|
|00000140| 6c 67 65 6e 64 65 6e 20 | 41 6c 67 6f 72 69 74 68 |lgenden |Algorith|
|00000150| 6d 75 73 0a 72 65 64 75 | 7a 69 65 72 74 20 73 69 |mus.redu|ziert si|
|00000160| 63 68 20 61 75 66 20 63 | 61 2e 20 31 2f 35 20 28 |ch auf c|a. 1/5 (|
|00000170| 6a 65 20 6e 61 63 68 20 | 44 69 63 68 74 65 29 2e |je nach |Dichte).|
|00000180| 0a 0a 09 09 09 09 09 4d | 61 72 6b 75 73 0a 0a 0a |.......M|arkus...|
|00000190| 0a 0a 0a 2f 2a 0a 20 2a | 20 66 69 6e 64 73 20 61 |.../*. *| finds a|
|000001a0| 6c 6d 6f 73 74 20 61 6c | 6c 20 61 75 67 6d 65 6e |lmost al|l augmen|
|000001b0| 74 69 6e 67 20 70 61 74 | 68 73 20 6f 66 20 6c 65 |ting pat|hs of le|
|000001c0| 6e 67 74 68 20 3c 3d 33 | 20 77 69 74 68 20 74 77 |ngth <=3| with tw|
|000001d0| 6f 20 70 61 73 73 65 73 | 20 6f 76 65 72 0a 20 2a |o passes| over. *|
|000001e0| 20 74 68 65 20 61 64 6a | 61 63 65 6e 63 79 20 6c | the adj|acency l|
|000001f0| 69 73 74 73 0a 20 2a 20 | 28 22 61 6c 6d 6f 73 74 |ists. * |("almost|
|00000200| 22 3a 20 64 69 73 63 6f | 76 65 72 79 20 6f 66 20 |": disco|very of |
|00000210| 61 20 62 6c 6f 73 73 6f | 6d 20 7b 76 2c 77 2c 78 |a blosso|m {v,w,x|
|00000220| 2c 76 7d 20 6c 65 61 64 | 73 20 74 6f 20 61 20 73 |,v} lead|s to a s|
|00000230| 6b 69 70 20 6f 66 20 74 | 68 65 0a 20 2a 20 65 64 |kip of t|he. * ed|
|00000240| 67 65 20 28 78 2c 76 29 | 2c 20 65 76 65 6e 20 69 |ge (x,v)|, even i|
|00000250| 66 20 74 68 65 20 62 61 | 73 65 20 76 20 73 74 61 |f the ba|se v sta|
|00000260| 79 73 20 75 6e 6d 61 74 | 63 68 65 64 20 2d 20 69 |ys unmat|ched - i|
|00000270| 74 27 73 20 6e 6f 74 20 | 77 6f 72 74 68 20 77 68 |t's not |worth wh|
|00000280| 69 6c 65 0a 20 2a 20 74 | 6f 20 66 69 78 20 74 68 |ile. * t|o fix th|
|00000290| 69 73 20 70 72 6f 62 6c | 65 6d 29 0a 20 2a 20 69 |is probl|em). * i|
|000002a0| 66 20 61 6c 6c 20 61 64 | 6a 61 63 65 6e 74 20 6e |f all ad|jacent n|
|000002b0| 6f 64 65 73 20 77 20 6f | 66 20 76 20 61 72 65 20 |odes w o|f v are |
|000002c0| 6d 61 74 63 68 65 64 2c | 20 74 72 79 20 74 6f 20 |matched,| try to |
|000002d0| 66 69 6e 64 20 61 6e 20 | 6f 74 68 65 72 20 0a 20 |find an |other . |
|000002e0| 2a 20 70 61 72 74 6e 65 | 72 20 66 6f 72 20 6d 61 |* partne|r for ma|
|000002f0| 74 65 5b 78 5d 2c 20 61 | 6e 64 20 6d 61 74 63 68 |te[x], a|nd match|
|00000300| 20 76 20 61 6e 64 20 77 | 20 6f 6e 20 73 75 63 63 | v and w| on succ|
|00000310| 65 73 73 0a 20 2a 2f 0a | 69 6e 74 20 68 65 75 72 |ess. */.|int heur|
|00000320| 69 73 74 69 63 28 20 67 | 72 61 70 68 20 26 47 2c |istic( g|raph &G,|
|00000330| 20 6e 6f 64 65 5f 61 72 | 72 61 79 28 6e 6f 64 65 | node_ar|ray(node|
|00000340| 29 26 20 6d 61 74 65 20 | 29 0a 7b 0a 20 20 6e 6f |)& mate |).{.  no|
|00000350| 64 65 20 75 2c 20 76 2c | 20 77 2c 20 78 20 3b 0a |de u, v,| w, x ;.|
|00000360| 20 20 69 6e 74 20 63 61 | 72 64 20 3d 20 30 20 3b |  int ca|rd = 0 ;|
|00000370| 0a 20 20 62 6f 6f 6c 20 | 66 6f 75 6e 64 20 3b 0a |.  bool |found ;.|
|00000380| 20 20 6e 6f 64 65 5f 61 | 72 72 61 79 28 62 6f 6f |  node_a|rray(boo|
|00000390| 6c 29 20 61 6c 6c 5f 6d | 61 74 63 68 65 64 28 20 |l) all_m|atched( |
|000003a0| 47 2c 20 66 61 6c 73 65 | 20 29 20 3b 0a 0a 20 20 |G, false| ) ;..  |
|000003b0| 47 2e 72 65 73 65 74 28 | 29 20 3b 0a 20 20 66 6f |G.reset(|) ;.  fo|
|000003c0| 72 61 6c 6c 5f 6e 6f 64 | 65 73 28 20 76 2c 20 47 |rall_nod|es( v, G|
|000003d0| 20 29 20 7b 09 09 0a 20 | 20 20 20 69 66 28 20 6d | ) {... |   if( m|
|000003e0| 61 74 65 5b 76 5d 3d 3d | 6e 69 6c 20 29 20 7b 09 |ate[v]==|nil ) {.|
|000003f0| 09 09 2f 2f 20 66 69 72 | 73 74 20 70 61 73 73 0a |..// fir|st pass.|
|00000400| 20 20 20 20 20 20 77 68 | 69 6c 65 28 20 28 66 6f |      wh|ile( (fo|
|00000410| 75 6e 64 3d 47 2e 6e 65 | 78 74 5f 61 64 6a 5f 6e |und=G.ne|xt_adj_n|
|00000420| 6f 64 65 28 20 77 2c 20 | 76 20 29 29 20 26 26 20 |ode( w, |v )) && |
|00000430| 28 6d 61 74 65 5b 77 5d | 21 3d 6e 69 6c 29 20 29 |(mate[w]|!=nil) )|
|00000440| 20 3b 0a 20 20 20 20 20 | 20 69 66 28 20 66 6f 75 | ;.     | if( fou|
|00000450| 6e 64 20 29 20 7b 0a 20 | 20 20 20 20 20 20 20 6d |nd ) {. |       m|
|00000460| 61 74 65 5b 76 5d 20 3d | 20 77 20 3b 20 20 6d 61 |ate[v] =| w ;  ma|
|00000470| 74 65 5b 77 5d 20 3d 20 | 76 20 3b 20 20 0a 09 63 |te[w] = |v ;  ..c|
|00000480| 61 72 64 2b 2b 20 3b 09 | 0a 20 20 20 20 20 20 7d |ard++ ;.|.      }|
|00000490| 0a 20 20 20 20 20 20 65 | 6c 73 65 20 7b 09 09 0a |.      e|lse {...|
|000004a0| 09 61 6c 6c 5f 6d 61 74 | 63 68 65 64 5b 76 5d 20 |.all_mat|ched[v] |
|000004b0| 3d 20 74 72 75 65 20 3b | 0a 09 47 2e 69 6e 69 74 |= true ;|..G.init|
|000004c0| 5f 61 64 6a 5f 69 74 65 | 72 61 74 6f 72 28 20 76 |_adj_ite|rator( v|
|000004d0| 20 29 20 3b 09 09 2f 2f | 20 73 65 63 6f 6e 64 20 | ) ;..//| second |
|000004e0| 70 61 73 73 0a 20 20 20 | 20 20 20 20 20 77 68 69 |pass.   |     whi|
|000004f0| 6c 65 28 20 47 2e 6e 65 | 78 74 5f 61 64 6a 5f 6e |le( G.ne|xt_adj_n|
|00000500| 6f 64 65 28 20 77 2c 20 | 76 20 29 20 29 20 7b 0a |ode( w, |v ) ) {.|
|00000510| 09 20 20 69 66 28 20 21 | 20 61 6c 6c 5f 6d 61 74 |.  if( !| all_mat|
|00000520| 63 68 65 64 5b 20 28 20 | 78 20 3d 20 6d 61 74 65 |ched[ ( |x = mate|
|00000530| 5b 77 5d 20 29 20 5d 20 | 29 20 7b 0a 20 20 20 20 |[w] ) ] |) {.    |
|00000540| 20 20 20 20 20 20 20 20 | 77 68 69 6c 65 28 20 28 |        |while( (|
|00000550| 66 6f 75 6e 64 3d 47 2e | 6e 65 78 74 5f 61 64 6a |found=G.|next_adj|
|00000560| 5f 6e 6f 64 65 28 20 75 | 2c 20 78 20 29 29 20 26 |_node( u|, x )) &|
|00000570| 26 20 28 20 28 75 3d 3d | 76 29 20 7c 7c 20 28 6d |& ( (u==|v) || (m|
|00000580| 61 74 65 5b 75 5d 21 3d | 6e 69 6c 29 20 29 20 29 |ate[u]!=|nil) ) )|
|00000590| 20 3b 0a 20 20 20 20 20 | 20 20 20 20 20 20 20 69 | ;.     |       i|
|000005a0| 66 28 20 66 6f 75 6e 64 | 20 29 20 7b 0a 20 20 20 |f( found| ) {.   |
|000005b0| 20 20 20 20 20 20 20 20 | 20 20 20 6d 61 74 65 5b |        |   mate[|
|000005c0| 75 5d 20 3d 20 78 20 3b | 20 20 6d 61 74 65 5b 78 |u] = x ;|  mate[x|
|000005d0| 5d 20 3d 20 75 20 3b 0a | 20 20 20 20 20 20 20 20 |] = u ;.|        |
|000005e0| 20 20 20 20 20 20 6d 61 | 74 65 5b 76 5d 20 3d 20 |      ma|te[v] = |
|000005f0| 77 20 3b 20 20 6d 61 74 | 65 5b 77 5d 20 3d 20 76 |w ;  mat|e[w] = v|
|00000600| 20 3b 0a 09 20 20 20 20 | 20 20 63 61 72 64 2b 2b | ;..    |  card++|
|00000610| 20 3b 0a 09 20 20 20 20 | 20 20 62 72 65 61 6b 20 | ;..    |  break |
|00000620| 3b 0a 09 20 20 20 20 7d | 0a 09 20 20 20 20 65 6c |;..    }|..    el|
|00000630| 73 65 0a 09 20 20 20 20 | 20 20 61 6c 6c 5f 6d 61 |se..    |  all_ma|
|00000640| 74 63 68 65 64 5b 78 5d | 20 3d 20 74 72 75 65 20 |tched[x]| = true |
|00000650| 3b 0a 09 20 20 7d 0a 09 | 7d 0a 20 20 20 20 20 20 |;..  }..|}.      |
|00000660| 7d 0a 20 20 20 20 7d 20 | 0a 20 20 7d 20 3b 0a 20 |}.    } |.  } ;. |
|00000670| 20 47 2e 72 65 73 65 74 | 28 29 20 3b 0a 0a 20 20 | G.reset|() ;..  |
|00000680| 72 65 74 75 72 6e 28 20 | 63 61 72 64 20 29 20 3b |return( |card ) ;|
|00000690| 0a 7d 0a 0a             |                         |.}..    |        |
+--------+-------------------------+-------------------------+--------+--------+